package com.gitee.feizns.explore.data_structure.graph;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;

/**
 * 332. 重新安排行程
 * @author feizns
 * @since 2020/2/28
 */
public class FindItinerary {

    static List<List<String>> list;

    static {
        list = new LinkedList<>();
        list.add(Arrays.asList("EZE","AXA"));
        list.add(Arrays.asList("TIA","ANU"));
        list.add(Arrays.asList("ANU","JFK"));
        list.add(Arrays.asList("JFK","ANU"));
        list.add(Arrays.asList("ANU","EZE"));
        list.add(Arrays.asList("TIA","ANU"));
        list.add(Arrays.asList("AXA","TIA"));
        list.add(Arrays.asList("TIA","JFK"));
        list.add(Arrays.asList("ANU","TIA"));
        list.add(Arrays.asList("JFK","TIA"));
    }

    public static void main(String[] args) {
//        System.out.println(findItinerary(list));
        Stack<String> ret = new Stack<>();
        ret.push("1");
        ret.push("2");
        ret.push("3");
        for (String s : ret) {
            System.out.println(s);
        }
    }

    private static G g;

    private static List<String> ret;

    public static List<String> findItinerary(List<List<String>> tickets) {
        g = create(tickets);
        ret = new LinkedList<>();
        dfs("JFK");
        Collections.reverse(ret);
        return ret;
    }

    private static void dfs(String s) {
        Set<String> adj = g.adj(s);
        if ( adj.isEmpty() ) {
            ret.add(s);
        } else {
            String next = adj.iterator().next();
            g.removeAdj(s, next);
            dfs(next);
            dfs(s);
        }
    }

    private static G create(List<List<String>> tickets) {
        G g = new G();
        for (List<String> ticket : tickets)
            g.add(ticket.get(0), ticket.get(1));
        return g;
    }

    private static class G {
        Map<String, Map<String, Integer>> g;
        public G() { g = new TreeMap<>(); }
        public int size() { return g.keySet().size(); }
        public void add(String s, String t) {
            Map<String, Integer> adj = g.get(s);
            if ( adj == null )
                adj = new TreeMap<>();
            Integer v = adj.get(t);
            if ( v == null )
                v  = 0;
            adj.put(t, v + 1);
            g.put(s, adj);
        }
        public Set<String> adj(String s) {
            Set<String> x = g.get(s).keySet();
            return x != null ? x : Collections.emptySet();
        }
        public void removeAdj(String s, String t) {
            Map<String, Integer> map = g.get(s);
            Integer v = map.get(t);
            if ( v == 1 )
                map.remove(t);
            else
                map.put(t, v - 1);
        }
    }

}
